Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 270 - Lining Up / arcila.cpp
bloba3e0ebd128ad7f28a7df85942cebedaf4c801acc
1 #include<sstream>
2 #include<iostream>
3 #include<stdio.h>
4 #include<math.h>
5 #include<algorithm>
6 #include<vector>
7 #include<map>
8 #include<string>
9 #define MAX(a,b) a>b?a:b
10 #define toPAngle(angle) angle>0?angle:(angle+pi)
11 #define D(X) cerr<<__LINE__<<" "<<#X<<" "<<x<<endl
12 const double pi=acos(-1);
13 using namespace std;
15 struct point{
16 double x,y;
17 point(){}
18 point(string a){
19 stringstream t(a);
20 t>>x>>y;
21 // D(x),D(y);
23 bool operator <(const point &t)const{
24 return x<t.x||(x==t.x &&y<t.y);
27 int main(){
28 int cases;
29 scanf("%d",&cases);
30 string aux;
31 getline(cin,aux);
32 getline(cin,aux);
33 for(int ans;cases-- && cin.peek()!=EOF;printf("%d\n",ans),cases<=0?:printf("\n")){
34 vector<point> p;
35 ans=2;
36 for(string dum;getline(cin,dum) && dum!="";p.push_back(point(dum)));
37 if(p.size()<3)continue;
38 sort(p.begin(),p.end());
39 double m;
40 for(int i=0;i<p.size()-1;++i){
41 map<double,int> angles;
42 for(int j=i+1;j<p.size();++j){
43 m=toPAngle(atan2(p[i].y-p[j].y,p[i].x-p[j].x));
44 if(angles.count(m))
45 ++angles[m];
46 else
47 angles[m]=2;
48 printf("%lf between (%lf, %lf) and (%lf, %lf), angles[m] = %d\n", m, p[i].x, p[i].y,
49 p[j].x, p[j].y, angles[m]);
50 ans=MAX(angles[m],ans);
54 return 0;